package com.grape.dsaa.algorithm.sort.core;

import com.grape.dsaa.algorithm.sort.Sorter;

/**
 * 描述:插入排序
 * 第i趟排序将数组第i+1个元素Ki+1插入到一個已经按值有序的子数组行（K1，K2...Ki）中的合适的位置，使得插入后的数组仍然保持有序
 * @author: myx
 * @date: 2019-04-29
 * Copyright © 2019-grape. All rights reserved.
 */
public class InsertionSorter implements Sorter {

	//最坏平均：O(n^2)
	//最好:O(n)
	@Override
	public void sort(int[] arr) {
		if(arr == null || arr.length <= 1) {
			return;
		}
		
		for(int i=1; i<arr.length; i++) {
			int elem = arr[i];
			int j = i - 1;
			
			while(j>=0 && elem < arr[j]) {
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = elem;
		}
		
		return;
 
	}

}
